int Prim(int G[N][N],int n,int u,int Lowcost[],int pre[]){
int S[N]={0}, sum=0; // sum存MST边权之和，作为函数返回值
for(int i=1;i<=n;i++){pre[i]=-1; Lowcost[i] = (i==u)? 0:INF;}
for(int i=1;i<=n;i++){ //把n个点逐个加入集合S
int v=FindMin(S,Lowcost,n); //从不在S中的点里选Lowcost值最小的点
if(v==-1) return sum; //不存在跨边，图不连通
S[v]=1; sum+=Lowcost[v]; //找到一条MST的边 (pre[v],v), v加入集合S
for(int w=1; w<=n; w++) //更新v邻接顶点的Lowcost和pre值
if(S[w]==0 && G[v][w]<Lowcost[w]){
Lowcost[w]=G[v][w]; pre[w]=v;
}
}
return sum;
}

void OutputMST(int Lowcost[],int pre[],int n){ //输出MST中的边
for(int v=1; v<=n; v++) //输出MST中的边 (pre[v],v)及权值
if(pre[v]!=-1)
printf(“edge:%d-%d,weight:%d\n”,pre[v],v,Lowcost[v]);
}

void BuildMST(Vertex Head[],int n,int Lowcost[],int pre[]){
//通过Lowcost和pre数组构建MST的邻接表
for(int v=1; v<=n; v++){
Edge *p = Head[v].adjacent; //将v的邻接顶点pre[v]插入邻接表
Head[v].adjacent = new Edge(pre[v],Lowcost[v],p);
p = Head[pre[v]].adjacent; //将pre[v]的邻接顶点v插入邻接表
Head[pre[v]].adjacent = new Edge(v,Lowcost[v],p);
}
}